SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>OPTICS algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">OPTICS algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r886047488">

/* start https://en.wikipedia.org/ */

.mw-parser-output .nobold{font-weight:normal}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar sidebar-collapse nomobile nowraplinks"><tbody><tr><td class="sidebar-pretitle">Part of a series on</td></tr><tr><th class="sidebar-title-with-pretitle"><a href="Machine_learning" title="Machine learning">Machine learning</a><br>and <a href="Data_mining" title="Data mining">data mining</a></th></tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Paradigms</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Supervised_learning" title="Supervised learning">Supervised learning</a></li>

<li><a href="Unsupervised_learning" title="Unsupervised learning">Unsupervised learning</a></li>

<li><a href="Semi-supervised_learning" class="mw-redirect" title="Semi-supervised learning">Semi-supervised learning</a></li>

<li><a href="Self-supervised_learning" title="Self-supervised learning">Self-supervised learning</a></li>

<li><a href="Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></li>

<li><a href="Meta-learning_(computer_science)" title="Meta-learning (computer science)">Meta-learning</a></li>

<li><a href="Online_machine_learning" title="Online machine learning">Online learning</a></li>

<li><a href="Batch_learning" class="mw-redirect" title="Batch learning">Batch learning</a></li>

<li><a href="Curriculum_learning" title="Curriculum learning">Curriculum learning</a></li>

<li><a href="Rule-based_machine_learning" title="Rule-based machine learning">Rule-based learning</a></li>

<li><a href="Neuro-symbolic_AI" title="Neuro-symbolic AI">Neuro-symbolic AI</a></li>

<li><a href="Neuromorphic_engineering" class="mw-redirect" title="Neuromorphic engineering">Neuromorphic engineering</a></li>

<li><a href="Quantum_machine_learning" title="Quantum machine learning">Quantum machine learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Problems</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Statistical_classification" title="Statistical classification">Classification</a></li>

<li><a href="Generative_model" title="Generative model">Generative modeling</a></li>

<li><a href="Regression_analysis" title="Regression analysis">Regression</a></li>

<li><a href="Cluster_analysis" title="Cluster analysis">Clustering</a></li>

<li><a href="Dimensionality_reduction" title="Dimensionality reduction">Dimensionality reduction</a></li>

<li><a href="Density_estimation" title="Density estimation">Density estimation</a></li>

<li><a href="Anomaly_detection" title="Anomaly detection">Anomaly detection</a></li>

<li><a href="Data_cleaning" class="mw-redirect" title="Data cleaning">Data cleaning</a></li>

<li><a href="Automated_machine_learning" title="Automated machine learning">AutoML</a></li>

<li><a href="Association_rule_learning" title="Association rule learning">Association rules</a></li>

<li><a href="Semantic_analysis_(machine_learning)" title="Semantic analysis (machine learning)">Semantic analysis</a></li>

<li><a href="Structured_prediction" title="Structured prediction">Structured prediction</a></li>

<li><a href="Feature_engineering" title="Feature engineering">Feature engineering</a></li>

<li><a href="Feature_learning" title="Feature learning">Feature learning</a></li>

<li><a href="Learning_to_rank" title="Learning to rank">Learning to rank</a></li>

<li><a href="Grammar_induction" title="Grammar induction">Grammar induction</a></li>

<li><a href="Ontology_learning" title="Ontology learning">Ontology learning</a></li>

<li><a href="Multimodal_learning" title="Multimodal learning">Multimodal learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><div style="display: inline-block; line-height: 1.2em; padding: .1em 0;"><a href="Supervised_learning" title="Supervised learning">Supervised learning</a><br><span class="nobold"><span style="font-size: 85%;">(<b><a href="Statistical_classification" title="Statistical classification">classification</a></b> • <b><a href="Regression_analysis" title="Regression analysis">regression</a></b>)</span></span> </div></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Apprenticeship_learning" title="Apprenticeship learning">Apprenticeship learning</a></li>

<li><a href="Decision_tree_learning" title="Decision tree learning">Decision trees</a></li>

<li><a href="Ensemble_learning" title="Ensemble learning">Ensembles</a>

<ul><li><a href="Bootstrap_aggregating" title="Bootstrap aggregating">Bagging</a></li>

<li><a href="Boosting_(machine_learning)" title="Boosting (machine learning)">Boosting</a></li>

<li><a href="Random_forest" title="Random forest">Random forest</a></li></ul></li>

<li><a href="Linear_regression" title="Linear regression">Linear regression</a></li>

<li><a href="Naive_Bayes_classifier" title="Naive Bayes classifier">Naive Bayes</a></li>

<li><a href="Artificial_neural_network" class="mw-redirect" title="Artificial neural network">Artificial neural networks</a></li>

<li><a href="Logistic_regression" title="Logistic regression">Logistic regression</a></li>

<li><a href="Perceptron" title="Perceptron">Perceptron</a></li>

<li><a href="Relevance_vector_machine" title="Relevance vector machine">Relevance vector machine (RVM)</a></li>

<li><a href="Support_vector_machine" title="Support vector machine">Support vector machine (SVM)</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Cluster_analysis" title="Cluster analysis">Clustering</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="BIRCH" title="BIRCH">BIRCH</a></li>

<li><a href="Hierarchical_clustering" title="Hierarchical clustering">Hierarchical</a></li>

<li><a href="K-means_clustering" title="K-means clustering"><i>k</i>-means</a></li>

<li><a href="Fuzzy_clustering" title="Fuzzy clustering">Fuzzy</a></li>

<li><a href="Expectation%E2%80%93maximization_algorithm" title="Expectation–maximization algorithm">Expectation–maximization (EM)</a></li>

<li><br><a href="DBSCAN" title="DBSCAN">DBSCAN</a></li>

<li><a href="Mean_shift" title="Mean shift">Mean shift</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Dimensionality_reduction" title="Dimensionality reduction">Dimensionality reduction</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Factor_analysis" title="Factor analysis">Factor analysis</a></li>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Structured_prediction" title="Structured prediction">Structured prediction</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Graphical_model" title="Graphical model">Graphical models</a>

<ul><li><a href="Bayesian_network" title="Bayesian network">Bayes net</a></li>

<li><a href="Conditional_random_field" title="Conditional random field">Conditional random field</a></li>

<li><a href="Hidden_Markov_model" title="Hidden Markov model">Hidden Markov</a></li></ul></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Anomaly_detection" title="Anomaly detection">Anomaly detection</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Random_sample_consensus" title="Random sample consensus">RANSAC</a></li>

<li><a href="Local_outlier_factor" title="Local outlier factor">Local outlier factor</a></li>

<li><a href="Isolation_forest" title="Isolation forest">Isolation forest</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Neural_network_(machine_learning)" title="Neural network (machine learning)">Neural networks</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Autoencoder" title="Autoencoder">Autoencoder</a></li>

<li><a href="Deep_learning" title="Deep learning">Deep learning</a></li>

<li><a href="Feedforward_neural_network" title="Feedforward neural network">Feedforward neural network</a></li>

<li><a href="Recurrent_neural_network" title="Recurrent neural network">Recurrent neural network</a>

<li><a href="Reservoir_computing" title="Reservoir computing">reservoir computing</a></li></ul></li>

<li><a href="Boltzmann_machine" title="Boltzmann machine">Boltzmann machine</a>

<ul><li><a href="Restricted_Boltzmann_machine" title="Restricted Boltzmann machine">Restricted</a></li></ul></li>

<li><a href="Diffusion_model" title="Diffusion model">Diffusion model</a></li>

<li><a href="Convolutional_neural_network" title="Convolutional neural network">Convolutional neural network</a>

<li><a href="LeNet" title="LeNet">LeNet</a></li>

<li><a href="AlexNet" title="AlexNet">AlexNet</a></li>

<li><a href="DeepDream" title="DeepDream">DeepDream</a></li></ul></li>

<li><a href="Neural_field" title="Neural field">Neural field</a>

<ul><li><a href="Neural_radiance_field" title="Neural radiance field">Neural radiance field</a></li>

<li><a href="Physics-informed_neural_networks" title="Physics-informed neural networks">Physics-informed neural networks</a></li></ul></li>

<li><a href="Transformer_(deep_learning_architecture)" title="Transformer (deep learning architecture)">Transformer</a>

<ul><li><a href="Vision_transformer" title="Vision transformer">Vision</a></li></ul></li>

<li><a href="Mamba_(deep_learning_architecture)" title="Mamba (deep learning architecture)">Mamba</a></li>

<li><a href="Spiking_neural_network" title="Spiking neural network">Spiking neural network</a></li>

<li><a href="Memtransistor" title="Memtransistor">Memtransistor</a></li>

<li><a href="Electrochemical_RAM" title="Electrochemical RAM">Electrochemical RAM</a> (ECRAM)</li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Q-learning" title="Q-learning">Q-learning</a></li>

<li><a href="Policy_gradient_method" title="Policy gradient method">Policy gradient</a></li>

<li><a href="State%E2%80%93action%E2%80%93reward%E2%80%93state%E2%80%93action" title="State–action–reward–state–action">SARSA</a></li>

<li><a href="Temporal_difference_learning" title="Temporal difference learning">Temporal difference (TD)</a></li>

<li><a href="Multi-agent_reinforcement_learning" title="Multi-agent reinforcement learning">Multi-agent</a>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Learning with humans</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Active_learning_(machine_learning)" title="Active learning (machine learning)">Active learning</a></li>

<li><a href="Crowdsourcing" title="Crowdsourcing">Crowdsourcing</a></li>

<li><a href="Human-in-the-loop" title="Human-in-the-loop">Human-in-the-loop</a></li>

<li><a href="Mechanistic_interpretability" title="Mechanistic interpretability">Mechanistic interpretability</a></li>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Model diagnostics</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Coefficient_of_determination" title="Coefficient of determination">Coefficient of determination</a></li>

<li><a href="Confusion_matrix" title="Confusion matrix">Confusion matrix</a></li>

<li><a href="Learning_curve_(machine_learning)" title="Learning curve (machine learning)">Learning curve</a></li>

<li><a href="Receiver_operating_characteristic" title="Receiver operating characteristic">ROC curve</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Mathematical foundations</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Kernel_machines" class="mw-redirect" title="Kernel machines">Kernel machines</a></li>

<li><a href="Bias%E2%80%93variance_tradeoff" title="Bias–variance tradeoff">Bias–variance tradeoff</a></li>

<li><a href="Computational_learning_theory" title="Computational learning theory">Computational learning theory</a></li>

<li><a href="Empirical_risk_minimization" title="Empirical risk minimization">Empirical risk minimization</a></li>

<li><a href="Occam_learning" title="Occam learning">Occam learning</a></li>

<li><a href="Probably_approximately_correct_learning" title="Probably approximately correct learning">PAC learning</a></li>

<li><a href="Statistical_learning_theory" title="Statistical learning theory">Statistical learning</a></li>

<li><a href="Vapnik%E2%80%93Chervonenkis_theory" title="Vapnik–Chervonenkis theory">VC theory</a></li>

<li><a href="Topological_deep_learning" title="Topological deep learning">Topological deep learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Journals and conferences</div><div class="sidebar-list-content mw-collapsible-content hlist">

<li><a href="Conference_on_Neural_Information_Processing_Systems" title="Conference on Neural Information Processing Systems">NeurIPS</a></li>

<li><a href="International_Joint_Conference_on_Artificial_Intelligence" title="International Joint Conference on Artificial Intelligence">IJCAI</a></li>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Related articles</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Glossary_of_artificial_intelligence" title="Glossary of artificial intelligence">Glossary of artificial intelligence</a></li>

<li><a href="List_of_datasets_for_machine-learning_research" title="List of datasets for machine-learning research">List of datasets for machine-learning research</a>

<ul><li><a href="List_of_datasets_in_computer_vision_and_image_processing" title="List of datasets in computer vision and image processing">List of datasets in computer vision and image processing</a></li></ul></li>

<li><a href="Outline_of_machine_learning" title="Outline of machine learning">Outline of machine learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

<p><b>Ordering points to identify the clustering structure</b> (<b>OPTICS</b>) is an algorithm for finding density-based<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> <a href="Cluster_analysis" title="Cluster analysis">clusters</a> in spatial data. It was presented in 1999 by Mihael Ankerst, Markus M. Breunig, <a href="Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Hans-Peter Kriegel</a> and Jörg Sander.<sup id="cite_ref-:0_2-0" class="reference"><a href="#cite_note-:0-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

Its basic idea is similar to <a href="DBSCAN" title="DBSCAN">DBSCAN</a>,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> but it addresses one of DBSCAN's major weaknesses: the problem of detecting meaningful clusters in data of varying density. To do so, the points of the database are (linearly) ordered such that spatially closest points become neighbors in the ordering. Additionally, a special distance is stored for each point that represents the density that must be accepted for a cluster so that both points belong to the same cluster. This is represented as a <a href="Dendrogram" title="Dendrogram">dendrogram</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Basic_idea">Basic idea</h2></div>

<p>Like <a href="DBSCAN" title="DBSCAN">DBSCAN</a>, OPTICS requires two parameters: <span class="texhtml mvar" style="font-style:italic;">ε</span>, which describes the maximum distance (radius) to consider, and <span class="texhtml mvar" style="font-style:italic;">MinPts</span>, describing the number of points required to form a cluster. A point <span class="texhtml mvar" style="font-style:italic;">p</span> is a <i>core point</i> if at least <span class="texhtml mvar" style="font-style:italic;">MinPts</span> points are found within its <span class="texhtml mvar" style="font-style:italic;">ε</span>-neighborhood <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{\varepsilon }(p)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{\varepsilon }(p)}</annotation>

</semantics>

</math></span><img src="./780d4a0a448c81c0df511e002c637df697330ccd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.843ex; height:2.843ex;" alt="{\displaystyle N_{\varepsilon }(p)}" loading="lazy"></span> (including point <span class="texhtml mvar" style="font-style:italic;">p</span> itself). In contrast to <a href="DBSCAN" title="DBSCAN">DBSCAN</a>, OPTICS also considers points that are part of a more densely packed cluster, so each point is assigned a <i>core distance</i> that describes the distance to the <span class="texhtml mvar" style="font-style:italic;">MinPts</span>th closest point:

</p>

<msub>

</mrow>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<mtext>UNDEFINED</mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<mtext>-th smallest distance in </mtext>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mtext>otherwise</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th smallest distance in }}N_{\varepsilon }(p)&{\text{otherwise}}\end{cases}}}</annotation>

</semantics>

</math></span><img src="./d94a92244682d386a5439536fe1bce492893f92c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:82.809ex; height:6.176ex;" alt="{\displaystyle {\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th smallest distance in }}N_{\varepsilon }(p)&{\text{otherwise}}\end{cases}}}" loading="lazy"></span></dd></dl>

<p>The <i>reachability-distance</i> of another point <span class="texhtml mvar" style="font-style:italic;">o</span> from a point <span class="texhtml mvar" style="font-style:italic;">p</span> is either the distance between <span class="texhtml mvar" style="font-style:italic;">o</span> and <span class="texhtml mvar" style="font-style:italic;">p</span>, or the core distance of <span class="texhtml mvar" style="font-style:italic;">p</span>, whichever is bigger:

</p>

<msub>

<mtext>reachability-dist</mtext>

</mrow>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<mtext>UNDEFINED</mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mtd>

<mtd>

<mtext>otherwise</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{reachability-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text{dist}}(p,o))&{\text{otherwise}}\end{cases}}}</annotation>

</semantics>

</math></span><img src="./b8342ce1c43f1293739af72255d216907da76e54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:90.329ex; height:6.176ex;" alt="{\displaystyle {\text{reachability-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text{dist}}(p,o))&{\text{otherwise}}\end{cases}}}" loading="lazy"></span></dd></dl>

<p>If <span class="texhtml mvar" style="font-style:italic;">p</span> and <span class="texhtml mvar" style="font-style:italic;">o</span> are nearest neighbors, this is the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon '<\varepsilon }">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon '<\varepsilon }</annotation>

</semantics>

</math></span><img src="./57bf3eb3ea4204cf93c5719c8a4907adeb933c3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.95ex; height:2.509ex;" alt="{\displaystyle \varepsilon '<\varepsilon }" loading="lazy"></span> we need to assume to have <span class="texhtml mvar" style="font-style:italic;">p</span> and <span class="texhtml mvar" style="font-style:italic;">o</span> belong to the same cluster.

</p><p>Both core-distance and reachability-distance are undefined if no sufficiently dense cluster (w.r.t. <span class="texhtml mvar" style="font-style:italic;">ε</span>) is available. Given a sufficiently large <span class="texhtml mvar" style="font-style:italic;">ε</span>, this never happens, but then every <span class="texhtml mvar" style="font-style:italic;">ε</span>-neighborhood query returns the entire database, resulting in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math></span><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"></span> runtime. Hence, the <span class="texhtml mvar" style="font-style:italic;">ε</span> parameter is required to cut off the density of clusters that are no longer interesting, and to speed up the algorithm.

</p><p>The parameter <span class="texhtml mvar" style="font-style:italic;">ε</span> is, strictly speaking, not necessary. It can simply be set to the maximum possible value. When a spatial index is available, however, it does play a practical role with regards to complexity. OPTICS abstracts from DBSCAN by removing this parameter, at least to the extent of only having to give the maximum value.

</p>

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<p>The basic approach of OPTICS is similar to <a href="DBSCAN" title="DBSCAN">DBSCAN</a>, but instead of maintaining known, but so far unprocessed cluster members in a set, they are maintained in a <a href="Priority_queue" title="Priority queue">priority queue</a> (e.g. using an indexed <a href="Heap_(data_structure)" title="Heap (data structure)">heap</a>).

</p>

<pre><b>function</b> OPTICS(DB, ε, MinPts) <b>is</b>

<b>for each</b> point p of DB <b>do</b>

p.reachability-distance = UNDEFINED

<b>for each</b> unprocessed point p of DB <b>do</b>

N = getNeighbors(p, ε)

mark p as processed

output p to the ordered list

<b>if</b> core-distance(p, ε, MinPts) != UNDEFINED <b>then</b>

Seeds = empty priority queue

update(N, p, Seeds, ε, MinPts)

<b>for each</b> next q in Seeds <b>do</b>

N' = getNeighbors(q, ε)

mark q as processed

output q to the ordered list

<b>if</b> core-distance(q, ε, MinPts) != UNDEFINED <b>do</b>

update(N', q, Seeds, ε, MinPts)

</pre>

<p>In update(), the priority queue Seeds is updated with the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon }</annotation>

</semantics>

</math></span><img src="./a30c89172e5b88edbd45d3e2772c7f5e562e5173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle \varepsilon }" loading="lazy"></span>-neighborhood of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math></span><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math></span><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"></span>, respectively:

</p>

<pre><b>function</b> update(N, p, Seeds, ε, MinPts) <b>is</b>

coredist = core-distance(p, ε, MinPts)

<b>for each</b> o in N

<b>if</b> o is not processed <b>then</b>

new-reach-dist = max(coredist, dist(p,o))

<b>if</b> o.reachability-distance == UNDEFINED <b>then</b> // o is not in Seeds

o.reachability-distance = new-reach-dist

Seeds.insert(o, new-reach-dist)

<b>else</b> // o in Seeds, check for improvement

<b>if</b> new-reach-dist < o.reachability-distance <b>then</b>

o.reachability-distance = new-reach-dist

Seeds.move-up(o, new-reach-dist)

</pre>

<p>OPTICS hence outputs the points in a particular ordering, annotated with their smallest reachability distance (in the original algorithm, the core distance is also exported, but this is not required for further processing).

</p>

<div class="mw-heading mw-heading2"><h2 id="Extracting_the_clusters">Extracting the clusters</h2></div>

</p><p>Using a <i>reachability-plot</i> (a special kind of <a href="Dendrogram" title="Dendrogram">dendrogram</a>), the hierarchical structure of the clusters can be obtained easily. It is a 2D plot, with the ordering of the points as processed by OPTICS on the x-axis and the reachability distance on the y-axis. Since points belonging to a cluster have a low reachability distance to their nearest neighbor, the clusters show up as valleys in the reachability plot. The deeper the valley, the denser the cluster.

</p><p>The image above illustrates this concept. In its upper left area, a synthetic example data set is shown. The upper right part visualizes the <a href="Spanning_tree" title="Spanning tree">spanning tree</a> produced by OPTICS, and the lower part shows the reachability plot as computed by OPTICS. Colors in this plot are labels, and not computed by the algorithm; but it is well visible how the valleys in the plot correspond to the clusters in above data set. The yellow points in this image are considered noise, and no valley is found in their reachability plot. They are usually not assigned to clusters, except the omnipresent "all data" cluster in a hierarchical result.

</p><p>Extracting clusters from this plot can be done manually by selecting ranges on the x-axis after visual inspection, by selecting a threshold on the y-axis (the result is then similar to a DBSCAN clustering result with the same <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon }</annotation>

</semantics>

</math></span><img src="./a30c89172e5b88edbd45d3e2772c7f5e562e5173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle \varepsilon }" loading="lazy"></span> and minPts parameters; here a value of 0.1 may yield good results), or by different algorithms that try to detect the valleys by steepness, knee detection, or local maxima. A range of the plot beginning with a steep descent and ending with a steep ascent is considered a valley, and corresponds to a contiguous area of high density. Additional care must be taken to the last points in a valley to assign them to the inner or outer cluster, this can be achieved by considering the predecessor.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Clusterings obtained this way usually are <a href="Hierarchical_clustering" title="Hierarchical clustering">hierarchical</a>, and cannot be achieved by a single DBSCAN run.

</p>

<div class="mw-heading mw-heading2"><h2 id="Complexity">Complexity</h2></div>

<p>Like <a href="DBSCAN" title="DBSCAN">DBSCAN</a>, OPTICS processes each point once, and performs one <a href="Fixed-radius_near_neighbors" title="Fixed-radius near neighbors"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon }</annotation>

</semantics>

</math></span><img src="./a30c89172e5b88edbd45d3e2772c7f5e562e5173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle \varepsilon }" loading="lazy"></span>-neighborhood query</a> during this processing. Given a <a href="Spatial_index" class="mw-redirect" title="Spatial index">spatial index</a> that grants a neighborhood query in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math></span><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"></span> runtime, an overall runtime of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\cdot \log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\cdot \log n)}</annotation>

</semantics>

</math></span><img src="./837218b6d28ce003c0f81f7af156da3ede782fe1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.41ex; height:2.843ex;" alt="{\displaystyle O(n\cdot \log n)}" loading="lazy"></span> is obtained. The worst case however is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math></span><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"></span>, as with DBSCAN. The authors of the original OPTICS paper report an actual constant slowdown factor of 1.6 compared to DBSCAN. Note that the value of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon }</annotation>

</semantics>

</math></span><img src="./a30c89172e5b88edbd45d3e2772c7f5e562e5173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle \varepsilon }" loading="lazy"></span> might heavily influence the cost of the algorithm, since a value too large might raise the cost of a neighborhood query to linear complexity.

</p><p>In particular, choosing <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon >\max _{x,y}d(x,y)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >\max _{x,y}d(x,y)}</annotation>

</semantics>

</math></span><img src="./9bca4d1bfd0d45f033c1672dd582aafc671381d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:15.439ex; height:4.176ex;" alt="{\displaystyle \varepsilon >\max _{x,y}d(x,y)}" loading="lazy"></span> (larger than the maximum distance in the data set) is possible, but leads to quadratic complexity, since every neighborhood query returns the full data set. Even when no spatial index is available, this comes at additional cost in managing the heap. Therefore, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon }</annotation>

</semantics>

</math></span><img src="./a30c89172e5b88edbd45d3e2772c7f5e562e5173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle \varepsilon }" loading="lazy"></span> should be chosen appropriately for the data set.

</p>

<div class="mw-heading mw-heading2"><h2 id="Extensions">Extensions</h2></div>

<p>OPTICS-OF<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> is an <a href="Anomaly_detection" title="Anomaly detection">outlier detection</a> algorithm based on OPTICS. The main use is the extraction of outliers from an existing run of OPTICS at low cost compared to using a different outlier detection method. The better known version <a href="Local_outlier_factor" title="Local outlier factor">LOF</a> is based on the same concepts.

</p><p>DeLi-Clu,<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> Density-Link-Clustering combines ideas from <a href="Single-linkage_clustering" title="Single-linkage clustering">single-linkage clustering</a> and OPTICS, eliminating the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon }</annotation>

</semantics>

</math></span><img src="./a30c89172e5b88edbd45d3e2772c7f5e562e5173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle \varepsilon }" loading="lazy"></span> parameter and offering performance improvements over OPTICS.

</p><p>HiSC<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> is a hierarchical <a href="Subspace_clustering" class="mw-redirect" title="Subspace clustering">subspace clustering</a> (axis-parallel) method based on OPTICS.

</p><p>HiCO<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> is a hierarchical <a href="Correlation_clustering" title="Correlation clustering">correlation clustering</a> algorithm based on OPTICS.

</p><p>DiSH<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> is an improvement over HiSC that can find more complex hierarchies.

</p><p>FOPTICS<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> is a faster implementation using random projections.

</p><p>HDBSCAN*<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> is based on a refinement of DBSCAN, excluding border-points from the clusters and thus following more strictly the basic definition of density-levels by Hartigan.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Availability">Availability</h2></div>

<p>Java implementations of OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO and DiSH are available in the <a href="ELKI" title="ELKI">ELKI data mining framework</a> (with index acceleration for several distance functions, and with automatic cluster extraction using the ξ extraction method). Other Java implementations include the <a href="Weka_(machine_learning)" class="mw-redirect" title="Weka (machine learning)">Weka</a> extension (no support for ξ cluster extraction).

</p><p>The <a href="GNU_R" class="mw-redirect" title="GNU R">R</a> package "dbscan" includes a C++ implementation of OPTICS (with both traditional dbscan-like and ξ cluster extraction) using a <a href="K-d_tree" title="K-d tree">k-d tree</a> for index acceleration for Euclidean distance only.

</p><p>Python implementations of OPTICS are available in the <a rel="nofollow" class="external text" href="https://pyclustering.github.io/">PyClustering</a> library and in <a href="Scikit-learn" title="Scikit-learn">scikit-learn</a>. HDBSCAN* is available in the <a rel="nofollow" class="external text" href="https://hdbscan.readthedocs.io/">hdbscan</a> library.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFKriegelKrögerSanderZimek2011" class="citation journal cs1">Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (May 2011). <a rel="nofollow" class="external text" href="https://portal.findresearcher.sdu.dk/da/publications/be8fe7b9-d5e2-415c-91bc-5ac6fa00994b">"Density-based clustering"</a>. <i>Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery</i>. <b>1</b> (3): <span class="nowrap">231–</span>240. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fwidm.30">10.1002/widm.30</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:36920706">36920706</a>.</cite></span>

</li>

<li id="cite_note-:0-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-:0_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFMihael_AnkerstMarkus_M._BreunigHans-Peter_KriegelJörg_Sander1999" class="citation conference cs1">Mihael Ankerst; Markus M. Breunig; <a href="Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Hans-Peter Kriegel</a>; Jörg Sander (1999). <i>OPTICS: Ordering Points To Identify the Clustering Structure</i>. ACM SIGMOD international conference on Management of data. <a href="ACM_Press" class="mw-redirect" title="ACM Press">ACM Press</a>. pp. <span class="nowrap">49–</span>60. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.6542">10.1.1.129.6542</a></span>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFMartin_EsterHans-Peter_KriegelJörg_SanderXiaowei_Xu1996" class="citation conference cs1"><a href="Martin_Ester" title="Martin Ester">Martin Ester</a>; <a href="Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Hans-Peter Kriegel</a>; Jörg Sander; Xiaowei Xu (1996). Evangelos Simoudis; Jiawei Han; Usama M. Fayyad (eds.). <i>A density-based algorithm for discovering clusters in large spatial databases with noise</i>. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). <a href="AAAI_Press" class="mw-redirect" title="AAAI Press">AAAI Press</a>. pp. <span class="nowrap">226–</span>231. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.1980">10.1.1.71.1980</a></span>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-57735-004-9</bdi>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFSchubertGertz2018" class="citation conference cs1 cs1-prop-long-vol">Schubert, Erich; Gertz, Michael (2018-08-22). <a rel="nofollow" class="external text" href="http://ceur-ws.org/Vol-2191/paper37.pdf"><i>Improving the Cluster Structure Extracted from OPTICS Plots</i></a> <span class="cs1-format">(PDF)</span>. Lernen, Wissen, Daten, Analysen (LWDA 2018). Vol. CEUR-WS 2191. pp. <span class="nowrap">318–</span>329 – via CEUR-WS.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFMarkus_M._BreunigHans-Peter_KriegelRaymond_T._NgJörg_Sander1999" class="citation book cs1">Markus M. Breunig; <a href="Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Hans-Peter Kriegel</a>; Raymond T. Ng; Jörg Sander (1999). <a rel="nofollow" class="external text" href="http://springerlink.metapress.com/content/76bx6413gqb4tvta/">"OPTICS-OF: Identifying Local Outliers"</a>. <a rel="nofollow" class="external text" href="https://lirias.kuleuven.be/handle/123456789/125270"><i>Principles of Data Mining and Knowledge Discovery</i></a>. Lecture Notes in Computer Science. Vol. 1704. <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. pp. <span class="nowrap">262–</span>270. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fb72280">10.1007/b72280</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-66490-1</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:27352458">27352458</a>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFAchtertBöhmKröger2006" class="citation conference cs1">Achtert, Elke; Böhm, Christian; Kröger, Peer (2006). "DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking". In Ng, Wee Keong; Kitsuregawa, Masaru; Li, Jianzhong; Chang, Kuiyu (eds.). <i>Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapore, April 9-12, 2006, Proceedings</i>. Lecture Notes in Computer Science. Vol. 3918. Springer. pp. <span class="nowrap">119–</span>128. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11731139_16">10.1007/11731139_16</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-33206-0</bdi>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFAchtertBöhmKriegelKröger2006" class="citation conference cs1">Achtert, Elke; Böhm, Christian; Kriegel, Hans-Peter; Kröger, Peer; Müller-Gorman, Ina; Zimek, Arthur (2006). "Finding Hierarchies of Subspace Clusters". In Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). <i>Knowledge Discovery in Databases: PKDD 2006, 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, September 18-22, 2006, Proceedings</i>. Lecture Notes in Computer Science. Vol. 4213. Springer. pp. <span class="nowrap">446–</span>453. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11871637_42">10.1007/11871637_42</a></span>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-45374-1</bdi>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFAchtertBöhmKrögerZimek2006" class="citation book cs1">Achtert, E.; Böhm, C.; Kröger, P.; Zimek, A. (2006). "Mining Hierarchies of Correlation Clusters". <i>18th International Conference on Scientific and Statistical Database Management (SSDBM'06)</i>. pp. <span class="nowrap">119–</span>128. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.707.7872">10.1.1.707.7872</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSSDBM.2006.35">10.1109/SSDBM.2006.35</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7695-2590-7</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2679909">2679909</a>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFAchtertBöhmKriegelKröger2007" class="citation conference cs1">Achtert, Elke; Böhm, Christian; Kriegel, Hans-Peter; Kröger, Peer; Müller-Gorman, Ina; Zimek, Arthur (2007). "Detection and Visualization of Subspace Cluster Hierarchies". In Ramamohanarao, Kotagiri; Krishna, P. Radha; Mohania, Mukesh K.; Nantajeewarawat, Ekawit (eds.). <i>Advances in Databases: Concepts, Systems and Applications, 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, April 9-12, 2007, Proceedings</i>. Lecture Notes in Computer Science. Vol. 4443. Springer. pp. <span class="nowrap">152–</span>163. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-71703-4_15">10.1007/978-3-540-71703-4_15</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-71702-7</bdi>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFSchneiderVlachos2013" class="citation journal cs1">Schneider, Johannes; Vlachos, Michail (2013). "Fast parameterless density-based clustering via random projections". <i>22nd ACM International Conference on Information and Knowledge Management (CIKM)</i>.</cite></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFCampelloMoulaviZimekSander2015" class="citation journal cs1">Campello, Ricardo J. G. B.; Moulavi, Davoud; Zimek, Arthur; Sander, Jörg (22 July 2015). "Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection". <i>ACM Transactions on Knowledge Discovery from Data</i>. <b>10</b> (1): <span class="nowrap">1–</span>51. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2733381">10.1145/2733381</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2887636">2887636</a>.</cite></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite id="CITEREFJ.A._Hartigan1975" class="citation book cs1">J.A. Hartigan (1975). <i>Clustering algorithms</i>. John Wiley & Sons.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-03" href="https://en.wikipedia.org/wiki/?title=OPTICS_algorithm&oldid=1293833341">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>